import numpy as np
import random
from copy import deepcopy
from vrp_model import VRPTWInstance, Customer, Vehicle


class Chromosome:
    """染色体结构体"""

    def __init__(self, genes, cost, routes, routes_dissum, routes_timeoff, vehicle_used):
        self.genes = genes  # 原始基因序列
        self.cost = cost  # 总成本（用于比较）
        self.routes = routes  # 解码路径
        self.routes_dissum = routes_dissum # 记录每条路径对应的总距离
        self.route_timeoff = routes_timeoff # 记录路径对应的早到或晚到分钟
        self.vehicle_used = vehicle_used # 使用车辆数


    def __lt__(self, other):
        """定义比较运算符用于排序"""
        return self.cost < other.cost


class EnhancedGeneticAlgorithm:
    def __init__(self, instance, pop_size, min_pop_size,
                 max_generations, crossover_rate,
                 mutation_rate, T):
        self.instance = instance          # 问题实例
        self.pop_size = pop_size          # 初始种群大小
        self.min_pop_size = min_pop_size  # 最小种群大小
        self.max_generations = max_generations  # 最大迭代次数
        self.crossover_rate = crossover_rate    # 交叉概率
        self.mutation_rate = mutation_rate      # 变异概率
        self.T = T                        # 种群调整周期
        self.current_pop_size = pop_size  # 当前种群大小
        self.generation = 0               # 当前已完成的迭代数

    '''种群初始化---不会产生重复个体'''
    def initialize_population(self):
        # 将配送点1-32放在列表customers中[1,2,3,...,32]
        customers = list(range(1, len(self.instance.customers)))
        return [random.sample(customers, len(customers)) for _ in range(self.pop_size)]


    '''计算适应度值，chromo为染色体即种群中的个体'''
    def calculate_fitness(self, chromo):
        key = tuple(chromo) # 将列表均转换为元组
        # 判断当前元组是否在适应度缓存的集合中，若在则返回该元素对应的适应度值
        if key in self.instance._fitness_cache:
            return self.instance._fitness_cache[key]

        routes = [] # 总路径---包含每辆车的路径
        routes_timeoff = [] # 记录每条路径对应的早到或晚到分钟
        routes_dissum = {} # 记录每条路径对应的总距离---以键值对形式存储
        cur_routes_timeoff = [0] # 记录当前车辆路径对应的早到或晚到分钟
        current_route = [0] # 当前车辆的路径
        total_cost = 0 # 总花费
        current_load = 0 # 车辆当前已使用的载重量
        current_volume = 0 # 车辆当前已使用的容积
        current_range = 0 # 车辆当前已行驶的路程
        current_time = 810 # 车辆从当前点出发下一点的时间（默认为13:30）
        vehicle_used = 0 # 车辆使用数

        # 对每一个客户点（即配送点）进行处理
        for customer_id in chromo:
            # 获取客户（即配送点）实例---获取指定Customer类的对象
            customer = self.instance.customers[customer_id]

            # 检查换车条件---判断当前车辆是否能够向当前客户（即配送点）送货
            ## 车辆当前载重量 + 下一个客户的货物需求量 > 最大载重量
            ## 车辆当前容积 + 下一个客户的货物容积 > 最大容积
            ## 车辆当前行驶里程 + 到达下一个客户的里程 > 最大里程 and 车辆当前行驶里程 + 返回里程 <= 最大里程
            ## 车辆当前行驶里程 + 到达下一个客户的里程 + 下一个客户点返回仓库的里程 > 最大里程 and 车辆当前行驶里程 + 返回里程 <= 最大里程
            if (current_load + customer.demand > self.instance.vehicle.capacity or
                current_volume + customer.volume > self.instance.vehicle.volume or
                (current_range + self.instance.distance_matrix[current_route[-1]][customer_id] > self.instance.vehicle.max_range
                 and current_range + self.instance.distance_matrix[current_route[-1]][0] <= self.instance.vehicle.max_range) or
                (current_range + self.instance.distance_matrix[current_route[-1]][customer_id] + self.instance.distance_matrix[customer_id][0] > self.instance.vehicle.max_range
                 and current_range + self.instance.distance_matrix[current_route[-1]][0] <= self.instance.vehicle.max_range)):

                # 计算返回成本
                return_distance = self.instance.distance_matrix[current_route[-1]][0]
                total_cost += return_distance * self.instance.vehicle.distance_cost  # 车辆运输成本
                total_cost += self.instance.vehicle.fixed_cost # 车辆固定成本

                current_range += return_distance  # 更新车辆当前已行驶的里程
                # 车辆充电成本
                total_cost += (self.instance.vehicle.charge_cost * current_range * self.instance.vehicle.charged_time) / self.instance.vehicle.max_range
                # 车辆充电占用的机会成本
                total_cost += (self.instance.vehicle.chance_cost * current_range * self.instance.vehicle.charged_time) / self.instance.vehicle.max_range
                vehicle_used += 1  # 车辆数
                # 记录路径
                current_route.append(0)
                routes.append(current_route)
                # 记录早到或迟到的分钟数
                cur_routes_timeoff.append(0)
                routes_timeoff.append(cur_routes_timeoff)
                # 键值对形式存储当前车辆送完货返回到仓库后行驶的总距离---键为当前是第几辆车
                routes_dissum[vehicle_used] = current_range

                # 新车初始化
                current_route = [0] # 当前车辆的路径
                cur_routes_timeoff = [0] # 当前车辆早到或迟到的分钟数
                current_load = 0  # 车辆当前已使用的载重量
                current_volume = 0  # 车辆当前已使用的容积
                current_range = 0  # 车辆当前已行驶的路程
                current_time = 810 # 车辆从当前点出发下一点的时间（默认为13:30）
            # 添加客户到当前路径
            from_node = current_route[-1]
            distance = self.instance.distance_matrix[from_node][customer_id]
            travel_time = self.instance.time_matrix[from_node][customer_id]

            # 时间处理
            arrival_time = current_time + travel_time # 车辆到达当前点的时间
            wait_time = max(customer.early - arrival_time, 0) # 早到时间
            time_violation = max(arrival_time - customer.late, 0) # 晚到时间
            if wait_time > time_violation : cur_routes_timeoff.append(+wait_time)
            else : cur_routes_timeoff.append(-time_violation)

            # 成本累计
            total_cost += distance * self.instance.vehicle.distance_cost # 运输成本
            total_cost += wait_time * self.instance.vehicle.early_arrive_penalty # 早到罚金
            total_cost += time_violation * self.instance.vehicle.late_arrive_penalty # 晚到罚金

            # 更新状态
            current_route.append(customer_id) # 将客户添加到当前车辆路线中
            current_load += customer.demand # 更新车辆当前载重量
            current_volume += customer.volume # 更新车辆当前已载容积
            current_range +=  distance # 更新车辆当前已行驶的里程
            # 更新车辆从当前点出发下一个点的时间
            if wait_time != 0 : current_time = customer.early + customer.staytime
            else : current_time = arrival_time + customer.staytime

        # 处理最后路径
        if len(current_route) > 1:
            return_distance = self.instance.distance_matrix[current_route[-1]][0]
            return_time = self.instance.time_matrix[current_route[-1]][0]
            total_cost += return_distance * self.instance.vehicle.distance_cost  # 车辆运输成本
            # total_cost += return_time * self.instance.vehicle.time_cost
            total_cost += self.instance.vehicle.fixed_cost  # 车辆固定成本
            current_range += return_distance # 记录最后一辆车行驶的总距离
            vehicle_used += 1  # 车辆数
            routes_dissum[vehicle_used] = current_range
            current_route.append(0)
            cur_routes_timeoff.append(0)
            routes_timeoff.append(cur_routes_timeoff)
            routes.append(current_route)

        # 缓存结果
        chromo_obj = Chromosome(chromo, total_cost, routes, routes_dissum, routes_timeoff, vehicle_used)
        self.instance._fitness_cache[key] = chromo_obj # 将该条染色体（即路径作为对象存储到字典中---以键值对存储）
        return chromo_obj


    '''部分匹配交叉pmx'''
    def pmx_crossover(self, parent1, parent2):
        size = len(parent1)
        p1, p2 = random.sample(range(size), 2)
        start, end = min(p1, p2), max(p1, p2)

        child1 = parent1[:start] + parent2[start:end] + parent1[end:]
        child2 = parent2[:start] + parent1[start:end] + parent2[end:]

        # 修复重复基因
        for child in [child1, child2]:
            seen = set()
            duplicates = []
            for i, gene in enumerate(child):
                if gene in seen:
                    duplicates.append(i)
                else:
                    seen.add(gene)
            missing = set(parent1) - seen
            for idx in duplicates:
                child[idx] = missing.pop()
        return child1, child2

    '''基于位置交叉pbx'''
    def pbx_crossover(self, parent1, parent2):
        size = len(parent1)
        num = random.randint(1, size - 10) # 可选的位置的个数最多为size-10个
        positions = sorted(random.sample(range(size), num))
        # 初始化子代1和子代2
        child1 = [-1] * (size)
        child2 = [-1] * (size)
        # 在选中的位置保留 parent1 的基因到 child1，parent2 的基因到 child2
        for pos in positions:
            child1[pos] = parent1[pos]
            child2[pos] = parent2[pos]
        # 填充 child1，保持 parent2 中基因的相对顺序
        child1_pos = 0
        for ele in parent2:
            if ele not in child1:
                while child1[child1_pos] != -1:
                    child1_pos += 1
                child1[child1_pos] = ele
        # 填充 child2，保持 parent1 中基因的相对顺序
        child2_pos = 0
        for ele in parent1:
            if ele not in child2:
                while child2[child2_pos] != -1:
                    child2_pos += 1
                child2[child2_pos] = ele
        return child1, child2

    '''两点交换变异'''
    def swap_mutation(self, chromo):
        if random.random() < self.mutation_rate:
            idx1, idx2 = random.sample(range(len(chromo)), 2)
            chromo[idx1], chromo[idx2] = chromo[idx2], chromo[idx1]
        return chromo

    '''循环种群减少技术CPR'''
    def cyclic_population_adjustment(self, gen):
        cycle = self.max_generations // self.T # 将最大迭代次数分为若干周期--每隔总代数的五分之一进行一次调整
        if gen % cycle == 0 and gen != 0: # 设置当前种群规模为原来的80%，且不少于最小种群中的个体数
            self.current_pop_size = max(self.min_pop_size, int(self.current_pop_size * 0.8))

    '''防御策略增强（数值型处理）'''
    def defense_strategy_enhancement(self, parent, population):
        fitness_values = [self.calculate_fitness(c).cost for c in population] # 获取种群中所有个体的目标函数值
        # 计算统计指标
        median_fitness = np.median(fitness_values) # 取种群中目标函数值的中位数
        std_fitness = np.std(fitness_values) # 计算种群中目标函数值的标准差
        current_fitness = self.calculate_fitness(parent).cost # 获取当前解的目标函数值
        # 判断是否触发防御策略
        return current_fitness > (median_fitness + 0.5 * std_fitness) # 若当前个体优于大多数个体，则代表不需要额外的防御增强，返回True；反之则为False

    '''
    自适应的选择压力机制进行选择操作
        选择压力会随着代数的增加逐渐减小。初期选择压力较大，意味着较优的个体会被优先选择；而随着代数的增加，
        选择压力逐渐减小，允许更多的随机性进入选择过程。这种方式能帮助算法在早期进行广泛的探索，在后期进行局部精细的优化。
        fitness_values：适应度值列表
    '''
    def cpo_selection(self, population, fitness_values):
        sorted_indices = np.argsort(fitness_values) # 返回适应度值（即目标函数值)从小到大的索引列表，表示对个体的排序
        population_size = len(population) # 获取种群大小
        # 获取选择压力值---会随着代数的增加逐渐减小---最大为0.8，最小为0.2
        selection_pressure = 0.8 - 0.6 * (self.generation / self.max_generations)
        # 种群中每个个体的排名---返回一个NumPy数组，即[1,2,...,population_size]
        # ranks = np.arange(1, population_size + 1)
        ranks = sorted_indices
        # 个体被选择的概率
        probabilities = 1 / (
                    population_size * (selection_pressure + (1 - selection_pressure) * ranks / population_size))
        # 归一化选择概率，使得所有个体的概率之和为1
        probabilities /= probabilities.sum()

        selected_indices = np.random.choice(
            population_size, # 即range(0,population_size)---可以选择的种群中的个体序号
            size=population_size, # 要选择的个体数量
            replace=True, # 是否可以选择重复个体
            p=probabilities # 每个个体被选择的概率数组
        )
        return [population[i] for i in selected_indices]

    '''整合算法：返回最优个体Chromosome对象，以及历史最优个体的目标函数值'''
    def solve(self):
        population = self.initialize_population() # 种群初始化
        best_solution = None # 记录最优个体
        best_fitness = float('inf') # 记录最优个体的适应度值（即目标函数值）
        history = [] # 记录每代最优个体

        # 迭代遍历
        for gen in range(self.max_generations):
            self.cyclic_population_adjustment(gen) # 循环种群减少技术CPR---更改self.current_pop_size值
            population = population[:self.current_pop_size] # 更新种群
            print("当前代数为：{}，当前种群大小：{}".format(gen, self.current_pop_size))

            # 适应度（目标函数值）计算
            fitness_objects = [self.calculate_fitness(c) for c in population]
            fitness_values = [f.cost for f in fitness_objects]

            # 选择
            selected = self.cpo_selection(population, fitness_values)

            # 交叉与变异
            new_population = []
            while len(new_population) < self.current_pop_size:
                parents = random.sample(selected, 2) # 选择两个父代---该方法选中的两个父代一定不同
                print("父代1：{}".format(parents[0]))
                print("父代2：{}".format(parents[1]))

                # 交叉操作
                if random.random() < self.crossover_rate:
                    # child1, child2 = self.pmx_crossover(parents[0], parents[1]) # pmx部分匹配交叉
                    child1, child2 = self.pbx_crossover(parents[0], parents[1]) # pbx基于位置交叉
                    print("交叉1：{}".format(child1))
                    print("交叉2：{}".format(child2))
                else:
                    child1, child2 = deepcopy(parents[0]), deepcopy(parents[1])
                # 变异操作，并将变异后的个体添加到新种群中
                new_population.extend([
                    self.swap_mutation(child1),
                    self.swap_mutation(child2)
                ])


            population = new_population[:self.current_pop_size]
            current_best = min(fitness_objects, key=lambda x: x.cost) # 获取目标函数值最小的对象---Chromosome
            # 更新最优个体
            if current_best.cost < best_fitness:
                best_solution = current_best
                best_fitness = current_best.cost

            history.append(best_fitness) # 记录历史迭代最优个体的目标函数值
            print(f"Generation {gen + 1}: Best Cost={best_fitness:.2f}元 Routes={len(best_solution.routes)}条 vehicle_used={best_solution.vehicle_used}")
            self.instance.clear_cache() # 清空适应度缓存
            self.generation += 1 # 记录当前已完成的代数

        return best_solution, history